import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * <p>
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：
 * s = "barfoothefoobarman",
 * words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 * 示例 2：
 * <p>
 * 输入：
 * s = "wordgoodgoodgoodbestword",
 * words = ["word","good","best","word"]
 * 输出：[]
 */
class Solution {

    public static void main(String[] args) {
        List<Integer> list = findSubstring("barfoothefoobarman", new String[]{"foo", "bar"});
        /*List<Integer> list = findSubstring("pjzkrkevzztxductzzxmxsvwjkxpvukmfjywwetvfnujhweiybwvvsrfequzkhossmootkmyxgjgfordrpapjuunmqnxxdrqrfgkrsjqbszgiqlcfnrpjlcwdrvbumtotzylshdvccdmsqoadfrpsvnwpizlwszrtyclhgilklydbmfhuywotjmktnwrfvizvnmfvvqfiokkdprznnnjycttprkxpuykhmpchiksyucbmtabiqkisgbhxngmhezrrqvayfsxauampdpxtafniiwfvdufhtwajrbkxtjzqjnfocdhekumttuqwovfjrgulhekcpjszyynadxhnttgmnxkduqmmyhzfnjhducesctufqbumxbamalqudeibljgbspeotkgvddcwgxidaiqcvgwykhbysjzlzfbupkqunuqtraxrlptivshhbihtsigtpipguhbhctcvubnhqipncyxfjebdnjyetnlnvmuxhzsdahkrscewabejifmxombiamxvauuitoltyymsarqcuuoezcbqpdaprxmsrickwpgwpsoplhugbikbkotzrtqkscekkgwjycfnvwfgdzogjzjvpcvixnsqsxacfwndzvrwrycwxrcismdhqapoojegggkocyrdtkzmiekhxoppctytvphjynrhtcvxcobxbcjjivtfjiwmduhzjokkbctweqtigwfhzorjlkpuuliaipbtfldinyetoybvugevwvhhhweejogrghllsouipabfafcxnhukcbtmxzshoyyufjhzadhrelweszbfgwpkzlwxkogyogutscvuhcllphshivnoteztpxsaoaacgxyaztuixhunrowzljqfqrahosheukhahhbiaxqzfmmwcjxountkevsvpbzjnilwpoermxrtlfroqoclexxisrdhvfsindffslyekrzwzqkpeocilatftymodgztjgybtyheqgcpwogdcjlnlesefgvimwbxcbzvaibspdjnrpqtyeilkcspknyylbwndvkffmzuriilxagyerjptbgeqgebiaqnvdubrtxibhvakcyotkfonmseszhczapxdlauexehhaireihxsplgdgmxfvaevrbadbwjbdrkfbbjjkgcztkcbwagtcnrtqryuqixtzhaakjlurnumzyovawrcjiwabuwretmdamfkxrgqgcdgbrdbnugzecbgyxxdqmisaqcyjkqrntxqmdrczxbebemcblftxplafnyoxqimkhcykwamvdsxjezkpgdpvopddptdfbprjustquhlazkjfluxrzopqdstulybnqvyknrchbphcarknnhhovweaqawdyxsqsqahkepluypwrzjegqtdoxfgzdkydeoxvrfhxusrujnmjzqrrlxglcmkiykldbiasnhrjbjekystzilrwkzhontwmehrfsrzfaqrbbxncphbzuuxeteshyrveamjsfiaharkcqxefghgceeixkdgkuboupxnwhnfigpkwnqdvzlydpidcljmflbccarbiegsmweklwngvygbqpescpeichmfidgsjmkvkofvkuehsmkkbocgejoiqcnafvuokelwuqsgkyoekaroptuvekfvmtxtqshcwsztkrzwrpabqrrhnlerxjojemcxel",
                new String[]{"dhvf", "sind", "ffsl", "yekr", "zwzq", "kpeo", "cila", "tfty", "modg", "ztjg", "ybty", "heqg", "cpwo", "gdcj", "lnle", "sefg", "vimw", "bxcb"});*/
        for (int integer : list) {
            System.out.println(integer);
        }
    }

    /**
     * n个n个处理，n为单词长度
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<>(16);
        int wordLength = words[0].length();
        int wordNum = words.length;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < wordLength; i++) {
            int left = i, right = i, count = 0;
            HashMap<String, Integer> tmpMap = new HashMap<>();
            while (right + wordLength <= s.length()) {
                // 每次都去n出来比较
                String w = s.substring(right, right + wordLength);
                right += wordLength;
                if (!map.containsKey(w)) {
                    count = 0;
                    left = right;
                    tmpMap.clear();
                } else {
                    tmpMap.put(w, tmpMap.getOrDefault(w, 0) + 1);
                    count++;
                    while (tmpMap.getOrDefault(w, 0) > map.getOrDefault(w, 0)) {
                        // 如果当前这个单词的数量超过了，一直去掉最左边的那个直到不超过当前的单词
                        String substring = s.substring(left, left + wordLength);
                        count--;
                        tmpMap.put(substring, tmpMap.getOrDefault(substring, 0) - 1);
                        left += wordLength;
                    }
                    if (count == wordNum) {
                        res.add(left);
                    }
                }
            }
        }
        return res;
    }

    /**
     * 思路是判断对应的位置后面的字符串是不是可以全部消费低这些单词
     *
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int loop = s.length() -  words.length * words[0].length();
        char[] chars = s.toCharArray();
        // 遍历s，判断对应的位置是否符合要求
        for (int i = 0; i <= loop; i++) {
            if (match(chars, i, words)) {
                result.add(i);
            }
        }
        return result;
    }

    public static boolean match(char[] chars, int i, String[] words) {
        String word;
        boolean match;
        boolean[] used = new boolean[words.length];
        do {
            match = false;
            for (int j = 0; j < words.length; j++) {
                if (!used[j]) {
                    // 如果当前单词未被使用
                    word = words[j];
                    int k;
                    for (k = 0; k < word.length(); k++) {
                        if (word.charAt(k) != chars[i + k]) {
                            break;
                        }
                    }
                    if (k == word.length()) {
                        // 如果全部匹配了,算作被使用
                        used[j] = true;
                        i += k;
                        // 判断是不是全部都被使用
                        if (allUsed(used)) {
                            return true;
                        } else {
                            // 如果没有则从头开始
                            match = true;
                            break;
                        }
                    }
                }
            }
        } while (match);
        return false;
    }

    /**
     * 判断是不是都被使用了
     *
     * @param used
     * @return
     */
    private static boolean allUsed(boolean[] used) {
        for (int i = 0; i < used.length; i++) {
            if (!used[i]) {
                return false;
            }
        }
        return true;
    }

    private static Set<String> all;

    /**
     * 遍历所有可能性再处理，当words很长时性能很差，可能性会变得非常多
     *
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring1(String s, String[] words) {
        System.out.println("start:" + System.currentTimeMillis());
        List<Integer> result = new ArrayList<>();
        all = new HashSet<>();
        // 找出所有可能性
        List<String> wordList = Arrays.asList(words);
        List<String> newTmpList;
        List<String> newList;
        for (String word : wordList) {
            newList = new ArrayList<String>(wordList);
            newList.remove(word);
            newTmpList = new ArrayList<>();
            newTmpList.add(word);
            getAllWordString(newTmpList, newList);
        }
        System.out.println("all:" + System.currentTimeMillis());
        // 从s中找出可能的
        int pos;
        for (String s1 : all) {
            pos = s.indexOf(s1);
            if (pos != -1) {
                result.add(pos);
                do {
                    pos = s.indexOf(s1, pos + 1);
                    if (pos != -1) {
                        result.add(pos);
                    }
                } while (pos != -1);
            }
        }
        System.out.println("end:" + System.currentTimeMillis());
        return result;
    }

    /**
     * 递归遍历所有可能性
     *
     * @param tmp
     * @param wordList
     */
    public static void getAllWordString(List<String> tmp, List<String> wordList) {
        if (wordList.size() == 0) {
            all.addAll(tmp);
        } else if (wordList.size() == 1) {
            String word = wordList.get(0);
            for (String s : tmp) {
                all.add(s + word);
            }
        } else {
            List<String> newTmpList;
            List<String> newWordList;
            for (String word : wordList) {
                newWordList = new ArrayList<String>(wordList);
                newWordList.remove(word);
                newTmpList = new ArrayList<>();
                for (String s : tmp) {
                    newTmpList.add(s + word);
                }
                getAllWordString(newTmpList, newWordList);
            }
        }
    }

}